In a [Singly Linked List](https://ricardoborges.dev/data-structures-in-typescript-linked-list), each node has only a pointer to the next node, and there are some ways to reverse it, the one that I want to show here doesn't require extra space.

In this algorithm, we start from the list's head, and we use three pointers, each one for **previous node**, **current node** and **next node**.
In the beginning, The **current** and the **next** points to the list's head, and the **previous** points to null. While the **current** are pointing to a node we do the following:

1. **next** point to its next node
2. **current.next** points to **previous node**
3. **previous node** points to the **current node**
4. **current node** points to **next node**

This loop continues until the current points to null, which will mean that we reached the end of the list. Like this:

```typescript
prev = null;
current = head;
next = head;

while (current !== null) {
  next = next.next;
  current.next = prev;
  prev = current;
  current = next;
}
```

A single iteration works like this:

![images](https://res.cloudinary.com/dje4crtui/image/upload/v1626015999/data%20structures/reverse-linked-list_yloqhh.png)

This algorithm may vary according to the Linked List implementation, using [this implementation](https://ricardoborges.dev/data-structures-in-typescript-linked-list), looks like this:

```typescript
function reverse(linkedList: LinkedList<number>) {
  let prev = null;
  let current = linkedList.head;
  let next = linkedList.head;

  while (current !== null) {
    next = next.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  linkedList.head = prev;
}

const linkedList = new LinkedList((a: number, b: number) => a === b);

linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);

reverse(linkedList);

linkedList.traverse();
```


There are some ways to reverse a Singly Linked List, the one that I want to show here doesn't require extra space.

How to reverse a Singly Linked List

A linked list is a data structure that holds objects arranged in a linear order, this order is determined by a pointer in each node.
Unlike an array, a linked list doesn't provide constant-time access to a particular index, you have to iterate through the list to find an element, on the other hand, is possible to add and remove items from the beginning of the list in a constant time.
Linked lists can be used to implement other data structures, such as stacks, queues, and graphs.

There are some types of linked lists: 

* **Singly linked list** - Each node has only a pointer to the next node. 
* **Doubly linked list** - Each node has pointers to both the previous and next node. 
* **Circular linked list** - The last node points to the first element.

### Representation

![linked list](https://res.cloudinary.com/dje4crtui/image/upload/v1622906568/data%20structures/linked-list_jdtg7y.png)

- **Head** - the first node
- **Tail** - the last node

### Basic operations

**Insertion** - It's possible to insert a new element anywhere in the list, you just have to take care of the pointers. If you are adding an element to the beginning the new node will pointer to the former head node. If you are appending to the tail, the former tail node will point to the new node. Now, if inserting between nodes, the previous node has to point to the new node which will point to the next node

**Deletion** - Follow a similar logic of insertion, if you want to remove a node from the middle of the list, you just have to make the target's previous node point to the target's next node. In a doubly-linked list, you have to take care of the previous pointer too.

**Traverse** - Each node has a point to next, so you start from the node head and follow the pointers until the last node, which will not point to any node (in a non-circular linked list)

```typescript
n = list.head

while n != null
    n = n.next

```

Here's an implementation of a singly linked list:

```typescript
class Node<T> {
  data: T;
  next: Node<T> | null = null;

  constructor(data: T) {
    this.data = data;
  }
}

class LinkedList<T> {
  head: Node<T> | null = null;
  comparator: (a: T, b: T) => boolean;

  constructor(comparator: (a: T, b: T) => boolean) {
    this.comparator = comparator;
  }

  append(data: T): void {
    if (!this.head) {
      this.head = new Node(data);
    } else {
      let current = this.head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = new Node(data);
    }
  }

   delete(data: T): void {
    if (!this.head) return;

    // Check if the head node is the node to be removed
    if (this.comparator(this.head.data, data)) {
      this.head = this.head.next;
      return;
    }

    let current = this.head.next;
    let previous = this.head;

    /**
     * Search for the node to be removed and keep track of its previous node
     *
     * If it were a double linked list, we could simply search the node
     * and it would have a pointer to the previous node
     **/
    while (current) {
      if (this.comparator(current.data, data)) {
        current = null;
      } else {
        previous = current;
        current = current.next;
      }
    }

    /**
     * set previous.next to the target.next, if the node target is not found,
     * the 'previous' will point to the last node,
     * since the last node hasn't next, nothing will happen
     **/
    previous.next = previous.next ? previous.next.next : null;
  }

  search(data: T): Node<T> | null {
    let current = this.head;
    while (current) {
      if (this.comparator(current.data, data)) {
        return current;
      }
      current = current.next;
    }
    return null;
  }

  traverse() {
    let current = this.head;
    while (current != null) {
      console.log(current.data);
      current = current.next;
    }
  }
}
```

### Runner technique

This technique consists in iterate through a linked list with two pointers, a slow and a fast which will be ahead of the slow pointer by *n* nodes.

![runner technique](https://res.cloudinary.com/dje4crtui/image/upload/v1622906568/data%20structures/runner_kkvdx4.png)

This is useful to solve some problems with a linked list, like detecting a cycle or finding the middle node of a linked list when you don't know its size.

```typescript
/** Finding the middle node of a linked list **/

let slow: LinkedListNode<number> | null | undefined = linkedList.head;
let fast: LinkedListNode<number> | null | undefined = linkedList.head?.next;

/**
 * The "fast" will move twice as fast as the "slow" one,
 * so at the moment the "fast" reaches the end of the list,
 * the "slow" will be in the middle of the list
 **/

while (fast) {
  slow = slow?.next;
  fast = fast?.next?.next;
}

console.log(slow);
```


Linked Lists have some advantages over arrays and can be used to implement other data structures, such as stacks, queues, and graphs.

Ricardo Borges

How to reverse a Singly Linked List

Data Structures in TypeScript - Linked List